// ArraysAndStrings.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void reverse2(string& str)
{
    auto start = str.begin();
    auto end = str.end();

    while (start < end)
    {
        swap (*start++, *--end);
    }
}

void TestReverse()
{
    string input = "123456789";
    reverse2(input);
    cout << input << endl;
}

void replaceSpaces(string& str)
{
    auto spaceCount = count(str.begin(), str.end(), ' ');
    if (spaceCount == 0)
    {
        return;
    }

    str.resize(str.length() + spaceCount * 2);
    auto start = str.rend();
    auto oriEnd = str.rbegin() + spaceCount * 2;
    auto newEnd = str.rbegin();
    while (oriEnd != start)
    {
        auto c = *oriEnd;

        if (*oriEnd == ' ')
        {
            *newEnd++ = '0';
            *newEnd++ = '2';
            *newEnd++ = '%';
        }
        else
        {
            *newEnd++ = *oriEnd;
        }

        oriEnd++;
    }
}

void testReplaceSpaces()
{
    string input = " 12   45   6   7 88 ";
    replaceSpaces(input);
    cout << input << endl;
}

void compress(string& input)
{
    string ret(input.length() * 2,  ' ');

    auto compressed = ret.begin();

    auto begin = input.begin();
    auto end = input.end();

    while (begin != end)
    {
        auto current = *begin;
        
        *compressed++ = current;
        unsigned int count = 1;

        while (++begin != end && *begin == current)
        {
            ++count;
        }

        auto countString = to_string(count);
        copy(countString.begin(), countString.end(), compressed);
        compressed += countString.length();
    }

    ret.resize(compressed - ret.begin());
    if (ret.length() < input.length())
    {
        swap(ret, input);
    }
}

void testCompress()
{
    string input = "bbaaaadddd";
    compress(input);
    cout << input << endl;
}

template<size_t n>
void rotate(int (&matrix)[n][n])
{
    pair<int, int> moved;

    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n - i; j++)
        {
            moved.first = i;
            moved.second = j;
            auto temp = matrix[j][n - j];

        }
    }
}

void tetRotate()
{
    int matrix[5][5] = 
    {{1, 2, 3, 4, 5},
    {11, 12, 13, 14, 15},
    {21, 22, 23, 24, 25},
    {31, 32, 33, 34, 35},
    {41, 42, 43, 44, 45}};

    rotate<5>(matrix);

    for (int row = 0; row < 5; row++)
    {
        for (int col = 0; col < 5; col++)
        {
            cout << col << ",";
        }
        cout << endl;
    }
}

template<size_t n>
void setZeros(int (&matrix)[n][n])
{
    vector<bool> rows(n, false);
    vector<bool> cols(n, false);

    for(int row = 0; row < n; row++)
    {
        for(int col = 0; col < n; col++)
        {
            if( matrix[row][col] == 0 )
            {
                rows[row] = true;
                cols[col] = true;
            }
        }
    }

    for(int row = 0; row < n; row++)
    {
        for(int col = 0; col < n; col++)
        {
            if (rows[row] || cols[col])
            {
                matrix[row][col] = 0;
            }
        }
    }
}

void testSetZeros()
{
    int matrix[5][5] = 
    {{1, 0, 3, 4, 5},
    {11, 12, 13, 14, 15},
    {21, 0, 23, 24, 25},
    {31, 32, 33, 0, 35},
    {41, 42, 43, 44, 0}};

    setZeros<5>(matrix);

    for (int row = 0; row < 5; row++)
    {
        for (int col = 0; col < 5; col++)
        {
            cout << matrix[row][col] << ",";
        }
        cout << endl;
    }
}

bool isRotation(string const& s1, string const& s2)
{
    string s = s1 + s1;
    return s.find(s2) != string::npos;
}

void testIsRotation()
{
    string s1 = "waterbottle";
    string s2 = "terbottlewa";
    string s3 = "terbottleaw";

    if (isRotation(s1, s2))
    {
        cout << s2 << " is rotation of " << s1 << endl;
    }

    if (isRotation(s1, s3))
    {
        cout << s3 << " is rotation of " << s1 << endl;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    TestReverse();
    testReplaceSpaces();
    testCompress();
    //tetRotate();
    testSetZeros();
    testIsRotation();

    cin.get();
    return 0;
}

